/*
*https://leetcode.cn/problems/length-of-longest-subarray-with-at-most-k-frequency
*2958. 最多 K 个重复元素的最长子数组
* medium, 彭珵 2024.9.4
* 滑动窗口
*/
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        int left = 0; // 左指针，表示当前窗口的起始位置
        int right = 0; // 右指针，表示当前窗口的结束位置
        unordered_map<int, int> cnt; // 用于记录当前窗口中每个元素的出现次数
        int n = nums.size(); // 数组的长度
        int ans = 0; // 记录最长子数组的长度

        // 遍历数组
        while (right < n) {
            int right_num = nums[right]; // 当前右指针指向的元素
            cnt[right_num]++; // 增加当前元素的计数

            // 当当前元素的计数超过 k 时，移动左指针
            while (cnt[right_num] > k) {
                int left_num = nums[left]; // 当前左指针指向的元素
                cnt[left_num]--; // 减少左指针指向元素的计数
                left++; // 移动左指针，缩小窗口
            }

            // 更新最长子数组的长度
            ans = max(ans, right - left + 1);
            right++; // 移动右指针，扩展窗口
        }

        return ans; // 返回最长子数组的长度
    }
};